import re

from pythonds.basic.stack import Stack


def infixToPostfix(infixexpr):
    prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}  # 记录操作符的优先级
    opStack = Stack()
    postfixlist = []

    tokenlist = re.findall(r'\w+|[+*/()-]',infixexpr)
    # 解析表达式到单词列表

    # tokenlist =  infixexpr.split() # 解析表达式到单词列表 # 每个操作数和操作符之间需要使用空格隔开

    for token in tokenlist:
        if token in "QWERTYUIOPASDFGHJKLMNBVCXZ" or token in "0123456789":
            postfixlist.append(token)
        elif token == "(":
            opStack.push(token)
        elif token == ")":
            toptoken = opStack.pop()
            while toptoken != '(':
                postfixlist.append(toptoken)
                toptoken = opStack.pop()
        else:
            while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
                postfixlist.append(opStack.pop())
            opStack.push(token)

    while not opStack.isEmpty():
        postfixlist.append(opStack.pop())
    return "".join(postfixlist)


print(infixToPostfix("(A+(B*C))"))
print(infixToPostfix(" ( A + ( B * C ) )"))
